Many modern communication systems involve a number of geographically dispersed transmitter-receivers which communicate with each other by way of a high data rate transmission channel. The transmission channel may be a broadcast channel, a fiber optic cable or an electromagnetic transmission line, or it may include transmissions among a number of Earth station transmitter-receivers by way of the transponder of an Earth satellite. Economic considerations suggest that when the capital cost of a communications system is large, the capacity (the maximum throughput) of the system be as large as possible. Capacity is at a maximum, or 100%, when a single transmitter operates continuously and uses the communication channel or transmission path to address one or more receivers. When more than one transmitter must use the transmission path, a problem arises relating to scheduling the transmitters for maximum system capacity. If the transmitters which are to share the transmission path are physically near each other, a scheduler may be connected to each transmitter to uniquely establish a transmission time for each transmitter depending upon the amount of data to be transmitted, its importance or like considerations. When the geographic distance between the transmitters is large, and there is therefore a time delay between the signals leaving the scheduler and the time at which they arrive at the transmitters to be controlled, the scheduler may not be efficient in adapting to the changing conditions at each transmitter.
One approach to multi-access on such high propagation delay channels is to partition the channel time in a fixed, predetermined manner. Such systems are known as time division multiple access (TDMA) systems. They are efficient when the user population includes a few users having high duty cycles. Many modern systems provide communication among interactive data terminals, which operate in low duty cycle burst modes. Time division multiple access is not efficient in this context, because the burst of data may not fill the allotted time, the unused portion of which is therefore wasted.
In response to the increasing need for communication over transmission paths having a time delay, schemes have evolved in which each transmitter-receiver (Tx/Rx) monitors the signal on the transmission path to determine whether the transmission path is active or idle, for scheduling transmissions during idle intervals. Because of the path delays, two or more transmitter-receivers might begin transmission at nearly the same time, unaware of each other's transmission. As a result, the transmission path would carry two or more signals simultaneously, causing a mutual interference known as a collision. Such collisions ordinarily make it impossible to correctly receive and decode the information carried by the signals, and the transmitted information is therefore effectively destroyed. When the information is destroyed by a collision, it must be retransmitted. Many procedures or protocols have been devised for monitoring the transmission path to establish the presence or absence of a carrier and for scheduling transmissions and retransmissions in order to maximize capacity. Carrier sensing systems of this general sort have capacities in excess of 80%. U.S. Pat. No. 4,234,952 issued Nov. 18, 1980, to Gable, for example, stops or truncates the transmission of an information packet when interference is noted during transmission of that packet. Once a transmission has been in progress for the end-to-end propagation time of the transmission path, all transmitters other than the one transmitting are inhibited and the transmission is completed without collision.
The problems associated with TDMA and carrier sensing systems have led to contention protocols intended to more efficiently utilize a high propagation delay transmission path for low duty cycle communications among a large number of users. In general, contention systems allow any transmitter-receiver to transmit a message at will. In the event that two transmitter-receivers transmit at overlapping times, a collision occurs, as in the case of the carrier sensing systems with long propagation delays. Each transmitter-receiver must determine the existence of such collisions and respond by retransmitting the information. The ALOHA contention protocol is an asynchronous or unslotted system in which a plurality of remote stations are connected to a central station by a single transmission path. The various remote stations transmit complete packets of data over the transmission path. Collisions are resolved by retransmission, at random times after the collision, of the data lost due to collision. The ALOHA system has a capacity of approximately 18 percent for low data rate transmissions. Thus, it has a relatively low maximum throughput due to the inefficiency associated with wasting the time of two transmission packets in the event of a slight overlap of packet transmission times. However, ALOHA has a relatively short average transmission delay, because a transmission which does not collide is transmitted immediately and received after only the path length delay.
Slotted or synchronous ALOHA is an improvement over simple ALOHA in which all transmissions occur in fixed non-overlapping time slots. By thus slotting or synchronizing transmissions, the vulnerable time for packet collision is reduced from a duration equal to two packet intervals to one packet interval, and the capacity therefore increases to 37%. The slotting requirement, however, increases the cost and complexity of the system. Also, both slotted and unslotted ALOHA are subject to further inefficiencies resulting from collisions among retransmitted packets.
The Selective Reject ALOHA technique is described by a Raychaudhuri article which appeared in the IEEE Transactions on Communication, Feb. 1984, pp. 148-154. This technique fills the practical requirement for a channel sharing technique which handles messages of variable length efficiently, without requiring time synchronization among stations. This system is similar to ALOHA in that it involves contention message transmission, with subpacketization of the messages, combined with a Selective Reject retransmission protocol. In Selective Reject retransmission, only the collided subpackets as retransmitted, and the retransmission occurs at a random time following the collision. Maximum throughput or capacity in the vicinity of 0.3 can be achieved with Selective Reject ALOHA, regardless of message length distribution.
A time slotted contention access protocol in which new transmissions are prevented from interfering with retransmissions provides up to approximately 49% capacity. This system is the Capetanakis tree algorithm, described in IEEE Transactions on Information Theory, September 1979, pp. 505-515, later refined by J. L. Massey and by R. G. Gallager. Tree algorithms achieve moderately high capacity on short propagation delay systems, but are not well suited to long propagation delay systems because the outcome of a slot transmission must be known before transmission on the next slot can begin.
A slotted contention access system entitled "Announced Retransmission Random Access (ARRA)" is described in U.S. patent application Ser. No. 873,446, filed June 6, 1986, in the name of Raychaudhuri, which is a continuation of Ser. No. 610,007 filed May 14, 1984 (now abandoned). The ARRA system pre-establishes the time at which a retransmission will occur in the event of a collision in a particular packet, and transmits this information together with the original packet in a manner which survives the collision. Thus, all transmitter-receivers are advised of the time at which retransmission will occur, and are programmed to inhibit transmission during the retransmission period. The ARRA system provides a capacity of approximately 53% for the less complex embodiments and as high as 60% in the more complex embodiments.
For some applications, the slotting or synchronization requirement of slotted ALOHA, Tree Algorithm Random Access or ARRA may be undesirable. An asynchronous contention access system entitled "Asynchronous Random Access Comnunication System With Collision Resolution Based On Time Of Arrival" is described in U.S. patent application Ser. No. 802,999 filed Nov. 29, 1985, in the name of Raychaudhuri. In this system, all data packets as transmitted have a fixed duration. When a collision occurs, at least that transmitter-receiver whose own packet was first among those colliding and that transmitter-receiver whose own packet was last among those colliding identify their own transmissions as being first and last, respectively, and can retransmit their packets of data in a scheduled manner which avoids further collisions. Other embodiments extend this concept to scheduled retransmission of those packets which were first, second, penultimate and last among those colliding. This asynchronous system achieves a capacity of approximately 0.41 in the simpler embodiments and approximately 0.51 in the more complex embodiments.
A random access communication system with scheduled data transmissions and asynchronous contention scheduling is described in U.S. patent application Ser. No. 905,506 filed Sept. 10, 1986, in the name of Raychaudhuri. In this system, relatively short fixed-duration reservation request packets are transmitted on an asynchronous, contention basis, which transmissions, if successfully received, result in scheduled transmission of random-length message packets. This system has a capacity of approximately 0.65 when the duration (T.sub.R) of the reservation request packet is about 1/10 the duration (T.sub.M) the associated message packet. For T.sub.R /T.sub.M =0.05, capacity in 0.78, and for T.sub.R /T.sub.M =0.025, capacity is 0.88. However, since a reservation request packet must be transmitted and successfully received, and only then is the message packet transmitted, there is a mandatory minimum delay, even for short messages during periods in which the system is lightly loaded.
A simple random-access burst communications system which can handle variable length messages with low average delay and with high capacity is desired.